#include<cstdio>//uncle-lu
#include<vector>
#include<queue>
#include<algorithm>
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

int n;
int line[100010];
std::priority_queue<int>qu1;// 大根
std::priority_queue<int, std::vector<int>, std::greater<int> >qu2; // 小根
int mid;

int main()
{
	read(n);
	for (int i = 1; i <= n; i++) 
		read(line[i]);
	mid = line[1];
	printf("%d\n", mid);
	for (int i = 2; i <= n; i++) 
	{
		if(line[i] > mid)
			qu2.push(line[i]);
		else
			qu1.push(line[i]);
		if(i%2)
		{
			if(qu1.size() > qu2.size())
			{
				qu2.push(mid);
				mid = qu1.top();
				qu1.pop();
			}
			if(qu2.size() > qu1.size())
			{
				qu1.push(mid);
				mid = qu2.top();
				qu2.pop();
			}
			printf("%d\n", mid);
		}
	}
	return 0;
}
